Leetcode Day 1
1 <= num <= 3999,输入的 int 换成级数表示,然后对 4 和 9 的情况做一下处理,可以吗?这个题目好像已经把程序给出来了。
那就先看是不是 4 或者 9,然后判断是哪一种,然后剪掉,然后
class Solution:
def intToRoman(self, num: int) -> str:
first_int = num % 10
if first_int == 4:
pass
elif first_int == 9:
pass
else:
写到这觉得好像写成级数更好处理,因为判断减法要写太多 if 了。
class Solution:
def expandToSeries(self, num: int) -> list:
# Assume we have a * 1000 + b * 100 + c * 10 + d * 1
a = num % 1000
b = (num - a * 1000) % 100
c = ...
def intToRoman(self, num: int) -> str:
直接转换成字符串。可以用列表推导式,此外,为什么不用一个table?
[expression for item in iterable if condition]class Solution:
def intToRoman(self, num: int) -> str:
thousands = ["", "M", "MM", "MMM"]
hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
num_list = [int(char) for char in str(num)]
result = thousands[num_list[0]] + hundreds[num_list[1]] + tens[num_list[2]] + ones[num_list[3]]
return result
a = num // 1000
b = (num % 1000) // 100
c = (num % 100) // 10
d = num % 10
result = thousands[a] + hundreds[b] + tens[c] + ones[d]
def int_to_roman_greedy(num: int) -> str:
# 值和符号的映射,必须从大到小排列
value_symbols = [
(1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"),
(90, "XC"), (50, "L"), (40, "XL"), (10, "X"), (9, "IX"),
(5, "V"), (4, "IV"), (1, "I")
]
roman_numeral = []
for value, symbol in value_symbols:
while num >= value:
roman_numeral.append(symbol)
num -= value
if num == 0: # 提前结束
break
return "".join(roman_numeral)
# 示例
print(f"1994 -> {int_to_roman_greedy(1994)}") # MCMXCIV
print(f"58 -> {int_to_roman_greedy(58)}") # LVIII
print(f"3 -> {int_to_roman_greedy(3)}") # III
通过
如果在某一步的数比距离大,那么结束。
感觉正着走完全就是穷举了,没有什么简化办法。
不,好像有,如果紧接着的下一位位数不变,那么跳到下一位肯定没问题。
当前位数
对于
class Solution:
def canJump(self, nums: List[int]) -> bool:
position = 0
j = 0
if nums[position] == 0:
return False
while j <= nums[position]:
if position + nums[position] < len(nums):
return True
elif nums[position + j] >= nums[position] - j:
position = position + j
j = 1
else:
j += 1
if position + nums[position] < len(nums): 这一句写反号了
提交:
再次修改
看出你最后懒了,判断太草率了。好好想想什么时候截止:
class Solution:
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
if n == 1:
return True
position = 0
j = 0
if nums[position] == 0:
return False
while j <= nums[position]:
if position + nums[position] >= len(nums) - 1:
return True
elif nums[position + j] >= nums[position] - j:
position = position + j
j = 1
else:
j += 1
return position == n + 1
还捉了个虫
class Solution: # 最终简洁版
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
max_reach = 0
for i in range(n):
if i > max_reach:
return False
max_reach = max(max_reach, i + nums[i])
# 优化:如果已经可以覆盖终点,没必要继续遍历
# if max_reach >= n - 1:
# return True
# 如果循环正常结束,说明最后一个位置 n-1 也是可达的 (i <= max_reach)
return True
哎,薄纱。